﻿using System;
using System.Collections.Generic;
using System.Linq;
using Algoritmia.Utils;
using Algoritmia.Utils.Backtracers;

namespace Algoritmia.Problems.GeneralizedCoinChange.OnlyQuantityModeling
{
    public class DynamicCoinChanger : SpaceSavingDynamicCoinChanger
    {
        private readonly Func<IEnumerable<KeyValuePair<int, int>>, IBacktracer<int,int>> _createBacktracer;

        public DynamicCoinChanger(DataStructures.Lists.IList<int> values, DataStructures.Lists.IList<double> weights = null,
                                    Func<IEnumerable<KeyValuePair<int,int>>,IBacktracer<int,int>> createBacktracer = null)
              : base(values,weights)
          {
              _createBacktracer = createBacktracer ?? (it => new DynamicBacktracer<int,int>(it));
          }

          public IEnumerable<int> Change(int Q)
          {
              var mem = new double[Q + 1];
              mem[0] = 0.0;
              var back = new int[Q + 1];
              back[0] = 0;
              for(int q = 1; q <= Q; q++)
              {
                  var i1 = Enumerable.Range(0, _n).Where(i => _values[i] <= q).ArgMin(i => mem[q - _values[i]] + _weights[i]);
                  mem[q] = mem[q - _values[i1]] + _weights[i1];
                  back[q] = q - _values[i1];
              }
              return _createBacktracer(back.Select((e, i) => new KeyValuePair<int, int>(i, e))).Backtrace(Q, (e, b) => e - b[e]);
          }
    }
}
